package com.le.enhance.class8;

import org.junit.Test;

/**
 * 换钱的方法数
 * 【题目】 给定数组 arr，arr 中所有的值都为正数且不重复。
 * 每个值代表一种面值的货币，每种面值 的货币可以使用任意张，再给定一个整数 aim，代表要找的钱数，
 * 求组成 aim 的方法数。
 * <p>
 * arr=[5,10,25,1]，aim=15 == > 6
 */
public class Code_02_CoinsMin {

    public static int minCoins1(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim <= 0) {
            return 0;
        }
        return process(arr, 0, aim);
    }

    /**
     * @param arr
     * @param index
     * @param rest  剩余钱数
     * @return 返回方法数
     */
    public static int process(int[] arr, int index, int rest) {
        if (index == arr.length) {
            // 剩余钱数为0, 则存在一种方法
            return rest == 0 ? 1 : 0;
        }
        int ways = 0; // 方法数
        for (int zhang = 0; zhang * arr[index] <= rest; zhang++) {
            ways += process(arr, index + 1, rest - arr[index] * zhang);
        }
        return ways;
    }

    // dp
    public static int process2(int[] arr, int aim) {
        int len = arr.length;
        int[][] dp = new int[len + 1][aim + 1];
        dp[len][0] = 1;
        for (int i = len - 1; i > -1; i--) {
            for (int rest = 0; rest <= aim; rest++) {
                // 依赖于当前位置的下一行位置和左边一个位置
                dp[i][rest] = dp[i + 1][rest];
                if (rest - arr[i] >= 0) {
                    dp[i][rest] += dp[i][rest - arr[i]];
                }
            }
        }
        return dp[0][aim];
    }


    @Test
    public void test() {
        int[] arr = {5, 10, 25, 1};
        System.out.println(minCoins1(arr, 15));
        System.out.println(process2(arr, 15));
    }
}
